/*
MIF32 TP4
ROUX Steve	10607327 
XIAO Yang		10609286
*/

#include "arch.h"
#include <stdlib.h>
#include <time.h>


/* créer une valeur infinie */
#define _INFINITE 999999

/* Valeurs F, A et NA */
char valeurs[3][3] = { "NA", "A", "F"};

/* Definition du graphe */
int **matrix;

int matrix_size = 6;

//#define CHRONO_MODE 

clock_t c_start, c_end;
double mpi_start, mpi_end, mpi_elapsed, c_elapsed;


void construire_matrix() {
	
	matrix = new  int*[matrix_size];

	for(int i=0; i<matrix_size; i++) {
	
		matrix[i] = new  int[matrix_size];
		for(int j=0; j<matrix_size; j++) {
			if( (i + j)%2 ) {
				matrix[i][j] = i + j;
			}
			else {
				matrix[i][j] = _INFINITE;
			}
		}
	}
}

void detruire_matrix() {
	
	for(int i=0; i<matrix_size; i++) {
	
		delete[] matrix[i];
	}
	
	delete[] matrix;
	
	matrix = NULL;
}

/* Identifiants globaux */
Coll_id c_id;

/*Structure de données pour l'algorithme de Prim */
class triplet{
public:
	int k;
	int w;
	int b;
	triplet(int _k=-1, int _w = _INFINITE, int _b = -1) { k=_k; w=_w; b=_b; }
	~triplet(){}
};

/* Paire de recherche */
typedef struct {
	int nb_proc;
	int nb_sommet;
	int w;
} paire;

void paire_min( paire * in, paire * in_out, int count ) {
	if( in->w < in_out->w ) {
		*in_out = *in;
	}
	else if( ( in->w == in_out->w ) && ( in->nb_proc < in_out->nb_proc ) ) {
		in_out->nb_proc = in->nb_proc;
		in_out->nb_sommet = in->nb_sommet;
	}
}

/* Initialisation */
void init_gid(int, char **){
	c_id.set();
}

/* Classe principale */
class Root_thread: public Thread{
private:
	int nb_col;		// nombre de colonnes à considérer
	triplet* s;		// tableau de triplets
	
public:

	Root_thread(): Thread((Tmf0_ptr)&Root_thread::body) {
  		
	}
	
	~Root_thread() {
		if(nb_col > 0)
			delete s;
		
		/*Destruction de la matrice generee */	
		//detruire_matrix();
         }

	void body(){
		
		fprintf(Sdf::trace,"\n\n\n ************** NOEUD %d ************** \n",Sdf::PROC_ID);
	
		int tmp, i;
		paire envoi, recois;
		
		#ifdef CHRONO_MODE
		for( int taille = 10; taille < 100000; taille *= 10 ) {
		
		matrix_size = taille;
		#endif
		
		/* Initialisation des données */
		init_proc();
		
		#ifdef CHRONO_MODE 
		/* Lancement de la mesure */
		c_start = clock();
		mpi_start = MPI_Wtime();
		#endif
		
		for( i=0; i<matrix_size-1; i++ ) {			
			// Recherche de l'arrete de poids minimum 
			envoi.nb_proc = Sdf::PROC_ID;
			if( ( tmp = search_min() ) >= 0 ) {
				envoi.nb_sommet = Sdf::PROC_ID+(tmp*Sdf::PROC_NB);
				envoi.w = s[tmp].w;
			}
			else {
				envoi.nb_sommet = -1;
				envoi.w = _INFINITE;
			}
		
			#ifndef CHRONO_MODE
			fprintf(Sdf::trace,"\nenvoie min local => paire = %d %d \n", envoi.nb_sommet, envoi.w );
			fflush(Sdf::trace);
			#endif
			
			// Réduction -diffusion du minimum trouvé 
			//recois = envoi;
			_Sdf<paire>::reduce( envoi, recois, 1, paire_min, c_id);
			
			#ifndef CHRONO_MODE
			fprintf(Sdf::trace,"recois min global => paire = %d %d \n", recois.nb_sommet, recois.w );
			fflush(Sdf::trace);
			#endif
			
			// Si le sommet qu'on a soumis est bien le minimum, on fixe ce sommet 
			if( recois.nb_sommet == Sdf::PROC_ID+(tmp*Sdf::PROC_NB) ) {
				s[ tmp ].b = 1;
			}

			/*PHASE2*/
			// Mettre à jour la liste de triplets 
			for(int k=0; k<nb_col; k++){
				// Si le sommet n'a pas encore été atteint, on l'initialise directement 
				if( 	( s[k].b == -1 ) 
					&& (matrix[recois.nb_sommet][Sdf::PROC_ID+(k*Sdf::PROC_NB)] != _INFINITE) ) {
					s[k] = triplet( recois.nb_sommet, 
							matrix[recois.nb_sommet][Sdf::PROC_ID+(k*Sdf::PROC_NB)], 
							0 ); 
				}
				// Si le sommet a été atteint et qu'il y a amélioration, alors on met à jour 
				else if( ( s[k].b == 0 )
					&& (matrix[recois.nb_sommet][Sdf::PROC_ID+(k*Sdf::PROC_NB)] != _INFINITE)
					&& ( s[k].w > matrix[recois.nb_sommet][Sdf::PROC_ID+(k*Sdf::PROC_NB)]) ) {
					s[k] = triplet( recois.nb_sommet, 
							matrix[recois.nb_sommet][Sdf::PROC_ID+(k*Sdf::PROC_NB)], 
							0 ); 
				}
			}
		}
		
		#ifdef CHRONO_MODE 
		/* Arret de la mesure */
		c_end = clock();	
		mpi_end = MPI_Wtime();		
		c_elapsed = ((double)c_end - c_start) / CLOCKS_PER_SEC;	/* Conversion en seconde */
		mpi_elapsed = mpi_end - mpi_start;	
		
		fprintf(Sdf::trace,"Temps d'execution sur proc %d: c:%4.4f, mpi:%4.4f ( nb sommets:%d, nb proc:%d ) \n",Sdf::PROC_ID,c_elapsed,mpi_elapsed,matrix_size,Sdf::PROC_NB);
		
		fflush(Sdf::trace);
		
		#endif
		
		#ifndef CHRONO_MODE
		fprintf(Sdf::trace, "\n========== RESULTAT ==========\n");
		for(int j=0; j<nb_col; j++){
			fprintf(Sdf::trace,"triplet %d (sommet %d) = [ %d %d %s ]\n", j, Sdf::PROC_ID+(j*Sdf::PROC_NB), s[j].k, s[j].w, valeurs[1+s[j].b]);
			
		}
		fflush(Sdf::trace);
		
		#endif	
		
		detruire_matrix();
		
		#ifdef CHRONO_MODE
		}
		#endif
	}
	
protected:
	void init_proc() {
		int i;
		
		/* Chaque processus construit la meme matrice */
		construire_matrix();
		
		/* Répartition des colonnes */
		nb_col = ( matrix_size / Sdf::PROC_NB );
		if(  Sdf::PROC_ID < (matrix_size % Sdf::PROC_NB) ) nb_col++;
		
		/* Initialisation du tableau de triplets */
		if(nb_col > 0){
			s = new triplet[nb_col];
			
			/* On commence à partir du sommet 0 */
			if(Sdf::PROC_ID == 0){
				s[ 0 ] = triplet(-1,0,1);
			}
		}
		
		/* Initialiser les sommets atteints */
		for(i=0; i<nb_col; i++){
			if( (matrix[0][Sdf::PROC_ID+(i*Sdf::PROC_NB)] != _INFINITE) && (s[i].b != 1) ){
				s[i] = triplet( 0, matrix[0][Sdf::PROC_ID+(i*Sdf::PROC_NB)], 0);
			}
			#ifndef CHRONO_MODE
			fprintf(Sdf::trace,"triplet %d (sommet %d) = [ %d %d %s ]\n", i, Sdf::PROC_ID+(i*Sdf::PROC_NB), s[i].k, s[i].w, valeurs[1+s[i].b]);
			#endif
		}	
		fflush(Sdf::trace);
  	}
  	
  	int search_min(){
  		int i;
  		int _min = -1;
  		for(i=0; i<nb_col; i++){
  			if((s[i].b == 0) && (s[_min].w > s[i].w)){
  				_min = i;
  			}
  		}
  		
  		return _min;
  	}
};

MAIN(Root_thread, init_gid, Sdf::empty_f, Sdf::empty_e)
